import sys


#打开文件
with open("Euler.txt", "r") as f:  # 打开文件
    data = f.read()  # 读取文件
# 数据处理
datalist=data.replace("\n"," ")
datalist=datalist.split(" ")
for i in range(len(datalist)):
  datalist[i]=int(datalist[i])
#获取n和m
n=int(datalist[0])
m=int(datalist[1])
datalist.pop(0)#用完出队列,方便处理
datalist.pop(0)
#处理余下序偶序列
datalist=[datalist[i:i + 2] for i in range(0, len(datalist), 2)]
for i in range(len(datalist)):
  datalist[i]=tuple(datalist[i])
eulerEdges =datalist


#写入文件
f = open('Euler_Ans.txt', 'a')
f.write(str(m)+'\n')
f.close()



start = 1  # 如果是欧拉道路必须从奇度起点开始
visitedEdges = [0 for i in range(len(eulerEdges))] #访问过的路 初始化包含和边数目相等的0的列表
queue = [] # 保存路径信息
eulerFlag = False


def isEuler():#判断是否欧拉路径
    allVisited = True
    for e in visitedEdges:#遍历所有边,检查是否有未访问
        if e == 0:
            allVisited = False

    if allVisited:#如果都访问
        if queue[0] == queue[len(queue) - 1]:#队列头是否等于队列尾
            return 1#欧拉回路
        else:
            return 2#欧拉道路
    return 0#不存在

def printPath(flag):#打印路径
    if flag == 1:
        print("欧拉回路:", end="")
    else:
        print("欧拉道路:", end="")
    for i in range(len(queue)):#循环输出
        if i < len(queue) - 1:
            print(queue[i], "-> ", end="")
            #写入文件
            f = open('Euler_Ans.txt', 'a')
            f.write(str(queue[i])+','+str(queue[i + 1])+'\n')
            f.close()
        else:
            print(queue[i])

    f = open('Euler_Ans.txt', 'a')
    f.write('"********************"\n')
    f.close()



# 搜索过程只保存一条路的状态的信息，搜索结束后stack,visited会恢复为初始状态
def dfs(u):
    queue.append(u)#加入队列
    flag = isEuler()  # 判断当前路径是不是欧拉路，如果是则打印文字信息
    if flag > 0:
        eulerFlag = True
        printPath(flag)

    for i in range(len(eulerEdges)):#遍历所有边
        if visitedEdges[i] == 1:#已访问的边跳过
            continue
        edge = eulerEdges[i]
        if edge[0] == u:
            visitedEdges[i] = 1#标记为已访问边
            dfs(edge[1])#以v点为起点迭代进行dfs
            queue.pop()  # 回溯时,弹出
            visitedEdges[i] = 0  # 重置访问状态

        elif edge[1] == u:#如果边是自回路
            visitedEdges[i] = 1
            dfs(edge[0])
            queue.pop()  # 将搜索过的点弹出队列
            visitedEdges[i] = 0  # 重置访问状态

dfs(start)
if not eulerFlag:
    print("已输出所有欧拉回路或欧拉道路")


